package hot100.logos71To80;

import java.util.PriorityQueue;

/**
 * @author logos
 * date 2025/7/17 13:00
 * @version v1.0
 * @Package hot100.logos71To80
 */
public class logos76 {

    /**
     * 76. 数据流的中位数
     * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&envId=top-100-liked
     */

    class MedianFinder {

        PriorityQueue<Integer> minHeap, maxHeap;

        public MedianFinder() {
            minHeap = new PriorityQueue<>((x, y) -> (x - y));
            maxHeap = new PriorityQueue<>((x, y) -> (y - x));
        }

        public void addNum(int num) {
            if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
                maxHeap.add(num);
            } else {
                minHeap.add(num);
            }
            balance();
        }

        private void balance() {
            if (Math.abs(minHeap.size() - maxHeap.size()) == 2) {
                if (minHeap.size() > maxHeap.size()) {
                    maxHeap.add(minHeap.poll());
                } else {
                    minHeap.add(maxHeap.poll());
                }
            }
        }

        public double findMedian() {
            if (maxHeap.size() == minHeap.size()) {
                return (maxHeap.peek() + minHeap.peek()) / 2.0;
            }
            return maxHeap.size() > minHeap.size() ? maxHeap.peek() : minHeap.peek();
        }
    }
}
